#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int ListLen(struct ListNode* p) {
    int rtn = 0;
    while (p != NULL) {
        rtn = rtn + 1;
        p = p->next;
    }
    return rtn;
}

bool ListAdd(struct ListNode* ans, struct ListNode* p1, struct ListNode* p2, int len1, int len2) {
    bool upper = false;
    if (ans != NULL) {
        if (len1 >= 0) {
            ans->val += p1->val;
            p1 = p1->next;
        }
        if (len2 >= 0) {
            ans->val += p2->val;
            p2 = p2->next;
        }
        if (ListAdd(ans->next, p1, p2, len1 + 1, len2 + 1)) {
            ans->val += 1;
        }
        if (ans->val >= 10) {
            ans->val -= 10;
            return true;
        }
    }
    return false;
}

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2) {
    // write code here
    struct ListNode* rtn = malloc(sizeof(struct ListNode) * 1);
    struct ListNode* tmp;
    int len1 = ListLen(head1);
    int len2 = ListLen(head2);
    int i, rlen;
    rlen = len1 > len2 ? len1 : len2;
    rtn->val = 0;
    rtn->next = NULL;
    tmp = rtn;
    for (i = 0; i < rlen; i++) {
        tmp->next = malloc(sizeof(struct ListNode));
        tmp = tmp->next;
        tmp->val = 0;
        tmp->next = NULL;
    }

    ListAdd(rtn, head1, head2, len1 - rlen - 1, len2 - rlen - 1);
    if (rtn->val == 0) {
        return rtn->next;
    }
    return rtn;
}